/*
 * @lc app=leetcode.cn id=797 lang=typescript
 *
 * [797] 所有可能的路径
 */

// @lc code=start

//  思路：图的遍历
//  类似dfs，但是要加上根节点，因此将撤销放到循环外面
//  参考：https://labuladong.github.io/algo/2/20/34/

//  复杂度：O(n*2^n) O(n)

function allPathsSourceTarget(graph: number[][]): number[][] {
    const res: number[][] = []
    const path: number[] = []

    const traverse = (graph: number[][], index: number, path: number[]) => {
        path.push(index)
        const len = graph.length
        // 到达终点
        if (index === len - 1) {
            res.push(path.slice())
            path.pop()
            return
        }
        // 递归遍历每个相邻节点
        for (const node of graph[index]) {
            traverse(graph, node, path)
        }
        path.pop()
    }

    traverse(graph, 0, path)
    return res

};
// @lc code=end
const graph = [[1, 2], [3], [3], []]
console.log(allPathsSourceTarget(graph))
